Efficient Convergent Maximum Likelihood Decoding on Tail-Biting Trellises

摘要

An algorithm for exact maximum likelihood(ML) decoding on tail-bitingtrellises is presented, which exhibits very good average case behavior. Anapproximate variant is proposed, whose simulated performance is observed to bevirtually indistinguishable from the exact one at all values of signal to noiseratio, and which effectively performs computations equivalent to at most tworounds on the tail-biting trellis. The approximate algorithm is analyzed, andthe conditions under which its output is different from the ML output arededuced. The results of simulations on an AWGN channel for the exact andapproximate algorithms on the 16 state tail-biting trellis for the (24,12)Extended Golay Code, and tail-biting trellises for two rate 1/2 convolutionalcodes with memories of 4 and 6 respectively, are reported. An advantage of ouralgorithms is that they do not suffer from the effects of limit cycles or thepresence of pseudocodewords.